package com.example.algorithm.greedy;

/**
 * 给定两个整数 A 和 B，返回任意字符串 S，要求满足：
 *  S 的长度为 A + B，且正好包含 A 个 'a' 字母与 B 个 'b' 字母；
 *  子串 'aaa' 没有出现在 S 中；
 *  子串 'bbb' 没有出现在 S 中。
 *
 *  示例 1：
 *
 *  输入：A = 1, B = 2
 * 输出："abb"
 * 解释："abb", "bab" 和 "bba" 都是正确答案。
 *
 *  示例 2：
 *
 *  输入：A = 4, B = 1
 * 输出："aabaa"
 */
public class Leetcode984_StrWithout3a3b {
    public static void main(String[] args) {
        int a = 4, b = 1;
//        a = 1; b = 3;
//        a = 2; b = 5;
//        a = 4; b = 1;
        System.out.println(new Solution().strWithout3a3b(a, b));
    }

    static class Solution {
        /**
         * 贪心:剩下的 a 多就拼接 "aab"，剩下的 b 多就拼接 "bba"，一样多就拼接 "ab"
         * @param a
         * @param b
         * @return
         */
        private String strWithout3a3b2(int a, int b) {
            StringBuilder sb = new StringBuilder();
            while (a > b && b > 0) {
                sb.append("aab");
                a -= 2;
                --b;
            }

            while (b > a && a > 0) {
                sb.append("bba");
                b -= 2;
                --a;
            }

            while (a == b && a > 0) {
                sb.append("ab");
                --a;
                --b;
            }

            while (a > 0) {
                sb.append('a');
                --a;
            }
            while (b > 0) {
                sb.append('b');
                --b;
            }
            return sb.toString();
        }

        /**
         * 贪心算法(尽可能多的匹配"aa"或者"bb")
         * a,b 必须满足条件: 2 * min(a, b) + 2 <= max(a, b)
         * 只有前两个已经写下的字母都是 x 的时候，下一个写入字符串中的字母才不应该选择它。
         * 设当前还需要写入字符串的 'a' 与 'b' 中较多的那一个为 x，如果我们已经连续写了两个 x 了，下一次应该写另一个字母。
         * 否则，我们应该继续写 x
         * @param a
         * @param b
         * @return
         */
        private String strWithout3a3b1(int a, int b) {
            StringBuilder sb = new StringBuilder();
            while (a > 0 || b > 0) {
                int len = sb.length();
                boolean writeA = false;

                if (len >= 2 && sb.charAt(len - 2) == sb.charAt(len - 1)) {
                    if (sb.charAt(len - 1) == 'b') writeA = true;// 已经连续写了两个'b',则当前只能写'a'
                } else {
                    if (a >= b) writeA = true; // a,b谁剩余得多当前就写谁
                }

                if (writeA) {
                    sb.append('a');
                    --a;
                } else {
                    sb.append('b');
                    --b;
                }
            }
            return sb.toString();
        }

        public String strWithout3a3b(int a, int b) {
            return strWithout3a3b2(a, b);
        }
    }
}
